COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a04.tex[106,phy] \today\hfill}

\newdimen\unit
\def\point#1 #2 {\rlap{\kern#1\unit
  \raise#2\unit\hbox to 0\unit{\hss$\scriptstyle\bullet$\hss}}}
\def\ycoord#1 {\rlap{\kern -0.2\unit
 \raise#1\unit\hbox{#1}}}
\def\xcoord#1 {\rlap{\kern#1\unit
 \lower0.2\unit\hbox to 0\unit
 {\hss #1\hss}}}

\bigskip\noindent
[Iterative Refinement]

\bigskip
Let's look for the square root of 20, a number which gives 20 when multiplied 
by itself.  There is  a more general question that will give us insight into 
the particular one (a typical mathematician's trick): what pairs of numbers 
can be multiplied to give~20?  Examples are 
$1\times 20$, $2\times 10$, $2.5\times 8$, $4\times 5$.  Given
one such number, say~7, we can find the other number by dividing  the first
into~20, getting $20/7 = 2.857$.  This matches up the numbers in pairs, except,
of course, that the square root of~20 is a wallflower, matched with itself.

These pairs are ``nested''; that is, given any two pairs, both numbers of one lie
between the numbers of the other.  For example,  2.5 and~8 both lie between 
2 and~10.  
It has to be this way.  If one number of a pair were less than~2, and another
were between 2 and~10, the product would be less than~20, so that pair would be 
no good.

The picture below illustrates this pairing:

\bigskip\bigskip\bigskip

$$\vbox{\hbox{\unit=.25in
\xcoord 0
\xcoord 1
%\xcoord 2
\xcoord 2.5
\xcoord 4
\xcoord 5
\xcoord 8
%\xcoord 10
\xcoord 15
\xcoord 20
\point 0 1
\point 1 1
%\point 2 1
\point 2.5 1
\point 4 1
\point 5 1
\point 8 1
%\point 10 1
\point 15 1
\point 20 1
\kern 20\unit
}}$$

\bigskip\noindent
The pair of numbers which are both $\sqrt{20}$ lies inside all the other pairs.

Given any pair of numbers, say 1 and 20, we can pick any number between them,
say~3, and its mate, $20/3 = 6.67$, which will also be between the first pair
of numbers.  The first pair contain $\sqrt{20}$  between them, and the second pair
contain it more closely.  In this way, we could keep finding numbers closer
and closer to~$\sqrt{20}$.

To program this for a computer, how can we arrange to pick a number between
the first pair?  In many ways, but an easy one is to add the numbers and divide
by~2.  Let's try this for several steps, starting with 1 and~20.  

$$\vcenter{\halign{\lft{#}\qquad&\lft{#}\qquad&\lft{#}$\;$&\lft{#}\cr
First pair:&20 and 1&average&10.5\cr
Second pair:&10.5 and 1.905&average&\phantom{1}6.202\cr
Third pair:&\phantom{1}6.202 and 3.225&average&\phantom{1}4.713\cr
Fourth pair:&\phantom{1}4.713 and 4.243&average&\phantom{1}4.478\cr
Fifth pair:&\phantom{1}4.478 and 4.466&average&\phantom{1}4.472\cr
Sixth pair:&\phantom{1}4.472 and 4.472\cr}}$$

The square root is between each of these pairs of numbers, so it is between
4.472 and 4.472 (actually 4.4722719), and 4.472 is the square root of~20.
All we had to do was to start with any pair, and keep getting closer pairs
until they were so close that we knew pretty accurately what $\sqrt{20}$ must be.

Starting with the first number of a pair, call it A; the second number of that
pair is $20/A$ and the first number of the next pair is $(A + 20/A)/2$. So we can
find the first number of each pair by this formula without bothering to get 
the other.				 

How do we know when we are finished?  When a pair of mated numbers are very
close together.  In that case, both are also very close to the numbers of the
next pair, so we can check that.  The larger number in successive pairs keeps
getting smaller until it stops changing; we can use this as a test to stop.






\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft April 16, 1984

\bye